package tests;


import java.util.Scanner;
    //斐波那契凤尾（错误）
    public class test18 {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            while (sc.hasNextInt()) {
                int n = sc.nextInt();
                int[] arr = new int[n];
                arr[1] = 1;
                arr[2] = 1;
                if (n == 1) {
                    System.out.println("1");
                    return;
                } else if (n == 2) {
                    System.out.println("2");
                } else {
                    for (int i = 3; i <= n; i++) {
                        arr[i] = arr[i - 1] + arr[i - 2];
                    }
                    System.out.println(arr[n] % 1000000);
                    return;
                }
            }
        }
    }


